//稀疏矩阵的三元组表表示法以及转置方法
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define ElementType int
#define TSM_ROWMAX 10
#define TSM_COLMAX 10

//三元组
typedef struct 
{
    int row, col;//非零元素行下标和列下标
    ElementType e;
}Triple;

//稀疏矩阵
typedef struct 
{
    Triple* data;//非零元素的三元组表
    int m, n, len;//矩阵行数，列数，非零元素个数
    int capacity;//容量
}TSMatrix;

//初始化稀疏矩阵
void TSMInite(TSMatrix* ps)
{
    assert(ps);
    ps->data = NULL;
    ps->m = TSM_ROWMAX;
    ps->n = TSM_COLMAX;
    ps->len = 0;
    ps->capacity = 0;
}

//销毁稀疏矩阵
void TSMDestroy(TSMatrix* ps)
{
    assert(ps);
    free(ps->data);
    ps->data = NULL;
    ps->len = 0;
    ps->capacity = 0;
}

//检查扩容
void CheckCapacity(TSMatrix* ps)
{
    assert(ps);
    if(ps->capacity == ps->len)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        Triple* tmp = (Triple*)realloc(ps->data, newcapacity * sizeof(Triple));
        if(tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->data = tmp;
        ps->capacity = newcapacity;
    }
}

//插入元素
void ElemInsert(TSMatrix* ps, Triple x)
{
    assert(ps);
    CheckCapacity(ps);
    if(ps->len == 0)
    {
        ps->data[ps->len] = x;
    }
    if(x.row < ps->data[0].row)
    {
        for(int j = ps->len; j > 0; j--)
        {
            ps->data[j] = ps->data[j - 1];
        }
        ps->data[0] = x;
    }
    else
    for(int i = 0; i < ps->len; i++)
    {
        if(x.row >= ps->data[i].row&&x.row <= ps->data[i + 1].row||i == ps->len - 1)
        {
            for(int j = ps->len; j > i + 1; j--)
            {
                ps->data[j] = ps->data[j - 1];
            }
            ps->data[i + 1] = x;
            break;
        }
    }
    ps->len++;
}

//打印元素
void TSMPrint(TSMatrix ps)
{
    for(int i = 0; i < ps.len; i++)
    {
        printf("row = %d col = %d e = %d\n", ps.data[i].row, ps.data[i].col, ps.data[i].e);
    }
    printf("\n");
}

//列序递增转置法
void TSMSwitch1(TSMatrix A, TSMatrix* B)
{
    assert(B);
    TSMDestroy(B);
    B->data = (Triple*)malloc(A.capacity * sizeof(Triple));
    B->capacity = A.capacity;
    B->len = A.len;
    B->m = A.n;
    B->n = A.m;
    int j = 0;//记录B当前空位
    for(int k = 0; k < A.n; k++)
    {
        for(int i = 0; i < A.len; i++)
        {
            if(A.data[i].col == k)
            {
                B->data[j].row = A.data[i].col;
                B->data[j].col = A.data[i].row;
                B->data[j].e = A.data[i].e;
                j++;
            }
        }
    }
}

//一次定位快速转置算法
void TSMSwitch2(TSMatrix A, TSMatrix* B)
{
    assert(B);
    TSMDestroy(B);
    B->data = (Triple*)malloc(A.capacity * sizeof(Triple));
    B->capacity = A.capacity;
    B->len = A.len;
    B->m = A.n;
    B->n = A.m;
    int num[B->m];
    int position[B->m];
    memset(num, 0, B->m * sizeof(int));
    memset(num, 0, B->m * sizeof(int));
    for(int i = 0; i < A.len; i++)
    {
        num[A.data[i].col]++;
    }
    position[0] = 0;
    for(int row = 1; row < B->m; row++)
    {
        position[row] = position[row - 1] + num[row - 1];
    }
    for(int i = 0; i < A.len; i++)
    {
        B->data[position[A.data[i].col]].row = A.data[i].col;
        B->data[position[A.data[i].col]].col = A.data[i].row;
        B->data[position[A.data[i].col]].e = A.data[i].e;
        position[A.data[i].col]++;
    }
}


int main()
{
    TSMatrix A;
    TSMatrix B;
    Triple x1 = {3, 5, 8};
    Triple x2 = {2, 7, 9};
    Triple x3 = {1, 4, 6};
    Triple x4 = {8, 9, 4};
    Triple x5 = {0, 1, 9};
    TSMInite(&A);
    TSMInite(&B);
    ElemInsert(&A, x1);
    ElemInsert(&A, x2);
    ElemInsert(&A, x3);
    ElemInsert(&A, x4);
    ElemInsert(&A, x5);
    TSMSwitch2(A, &B);
    TSMPrint(A);
    TSMPrint(B);
    TSMDestroy(&A);
    TSMDestroy(&B);
    return 0;
}